public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }
    //判断两颗二叉树树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null && q != null || p != null && q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    //判断一棵树是否包含了另一颗树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot==null){
            return true;
        }else if(root==null){
            return false;
        }
        //这里比较root树和subRoot树是否相同，然后再递归root左数和右树
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSameTree(root,subRoot);//只要返回一个true 说明就包含了
    }
    //倒转一棵二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        //交换每个节点的左子树和右子树
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        //继续往下遍历
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断一棵二叉树是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftHight = height(root.left);
        int rightHight = height(root.right);
        if((rightHight-leftHight>1)||(leftHight-rightHight>1)){
            return false;
        }
        //没有则继续遍历
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    //先写一个算二叉树高度的函数
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int height = Max(height(root.left),height(root.right))+1;
        return height;
    }
    //比较大小
    public int Max(int num1,int num2){
        if(num1>=num2){
            return num1;
        }else{
            return num2;
        }
    }
}
